Run-length encoding (RLE) is a way to compress data such that, many times, the compressed data can be represented using less bits than the original (uncompressed) representation of the data. More specifically, to perform RLE on a particular data item, one or more runs of data within the particular data item are identified. A run of data is composed of a particular data value that repeatedly occurs in sequence. For example, the string “aaaabbbbccccc” is a run of four ‘a’ characters followed by a run of four ‘b’ characters followed by a run of five ‘c’ characters. As a further example, the string “123123123123123123123” is a run of seven occurrences of the data value “123”. RLE causes a run of data to be represented as the data value that is repeated (e.g., ‘a’) and the number of repetitions of the value (e.g., four).
Many times, this type of encoding reduces the number of bits required to represent a string of characters that contains one or more data runs. For example, using a shorthand representation of run-length encoding, the string “aaaabbbbccccc” can be represented as the run-length-encoded value 4a4b5c, which may be represented with less bits than the unencoded representation of the string would require. As such, RLE is a useful tool for compressing data.
Generally, the decompressing of RLE-encoded values is performed based on high-level computing instructions (such as instructions written in Java, C++, etc.) which are compiled into low-level instructions and/or machine code that accomplish the tasks requested in the high-level instructions. The compiled low-level instructions are not always optimized for the fastest performance of the requested tasks. This lack of optimization can slow down functions that require decompression of RLE-encoded values. As such, it would be beneficial to optimize decompression of RLE-encoded values at the hardware level.
The approaches described in this section are approaches that could be pursued, but not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated, it should not be assumed that any of the approaches described in this section qualify as prior art merely by virtue of their inclusion in this section.